package test_4_26;




public class Solution1 {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

    public static void main(String[] args) {
        ListNode node1=new ListNode(1);
        ListNode node2=new ListNode(4);
        ListNode node3=new ListNode(3);
        node1.next=node2;
        node2.next=node3;
        ListNode Node1=new ListNode(2);
        ListNode Node2=new ListNode(5);
        ListNode Node3 =new ListNode(2);
        node3.next=Node1;
        Node1.next=Node2;
        Node2.next=Node3;
        ListNode l3=partition(node1,2);
        display(l3);
    }
    public static ListNode partition(ListNode head, int x) {
        if(head==null)
        {
            return null;
        }

        ListNode cur=head;
        ListNode as=new ListNode(0);
        ListNode ae=as;
        ListNode bs=new ListNode(0);
        ListNode be=bs;
        while(cur!=null)
        {
            if(cur.val<x)
            {
                ae.next=cur;
                ae=ae.next;
            }
            else
            {
                be.next=cur;
                be=be.next;
            }
            cur=cur.next;
        }
        if(ae==null)
        {
            return bs.next;
        }
        if(be==null)
        {
            return as.next;
        }
        ae.next=bs.next;
        return as.next;

    }
    public static void display(ListNode head)
    {
        if(head==null)
        {
            return ;
        }
        while(head!=null)
        {
            System.out.print(head.val+" ");
            head=head.next;
        }
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null && l2==null)
        {
            return null;
        }
        if(l1!=null && l2==null)
        {
            return l1;
        }
        if(l2!=null && l1==null)
        {
            return l2;
        }
        ListNode l3=new ListNode(0);
        ListNode node=l3;

        while(l1!=null && l2!=null)
        {
            if(l1.val<l2.val)
            {
                node=l1;
                l1=l1.next;
            }
            else
            {
                node=l2;
                l2=l2.next;
            }
            node=node.next;
        }
        if(l1!=null)
        {
            node=l1;
        }
        else{
            node=l2;
        }
        return l3.next;
    }
}